題目連結: Word Pattern

題目描述為給定兩字串 pattern,str，要我們判別此兩字串是否有相同型式。其中字串 pattern 只包含小寫英文字母，字串 str 只包含空白與小寫英文字母，且 str 開頭不為空白。str 會被空白字元切成許多子字串，而 str 中的每個子字串只間隔一個空白字元。此題的相同型式類似 day14-Isomorphic Strings 中的同構，我們需要判斷 pattern 的每個字元是否與 str 中的非空子字串滿足bijection。

例子 1: pattern = "abba", s = "dog cat cat dog" , output= true。
例子 2: pattern = "abba", s = "dog cat cat fish" , output= false。
例子 3: pattern = "aaaa", s = "dog cat cat dog" , output= false。

思路 1 : Hash 法

我們可以仿造 day14 小結中提到的解法 2，將 pattern 的每個字元與 str 中的非空子字串互相對應，判別是否一致。

• 複雜度評估
  當 pattern 字串長度為 N 時，而 str 字串長度為 M 時，我們需要遍歷此兩個陣列，時間複雜度為 O(N+M)。此方法建立了 []string來儲存 str 的非空子字串以及兩個 map 來儲存每個字元對應的數值，空間複雜度為O(N+M)。

參考程式碼

func wordPattern(pattern string, str string) bool {
    
    ss := strings.Split(str, " ")
    mp:= make(map[byte]string)
    ms:=make(map[string]byte)
    
    var p byte
    var s string
    var okp,oks bool
    
    if len(pattern)!=len(ss){
        return false
    }
    
    for i:=0;i<len(pattern);i++{     
       p,s=pattern[i],ss[i]
       _,okp=mp[p]
       _,oks=ms[s]
      
        if !okp && !oks{
            mp[p]=s
            ms[s]=p
        } 
        
        if mp[p]!=s  || ms[s]!=p{
            return false
        }
        
    }
    
  
    return true
}

小結:

此題使用的概念與 day14 解法 2 一致，在本題的解法 1 中使用了輔助函式 strings.Split 來預先分割 str 的非空子字串，讓我們可以專注在判別相同型式上，我將解法 1 加上簡單的測試，上傳程式碼到此。